package algorithmTopics.other;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution {

/*    给你一个下标从 0 开始长度为 3 的整数数组 nums ，需要用它们来构造三角形。
    如果一个三角形的所有边长度相等，那么这个三角形称为 equilateral 。
    如果一个三角形恰好有两条边长度相等，那么这个三角形称为 isosceles 。
    如果一个三角形三条边的长度互不相同，那么这个三角形称为 scalene 。
    如果这个数组无法构成一个三角形，请你返回字符串 "none" ，否则返回一个字符串表示这个三角形的类型。
    示例 1：
    输入：nums = [3,3,3]
    输出："equilateral"
    解释：由于三条边长度相等，所以可以构成一个等边三角形，返回 "equilateral" 。*/

    public String triangleType(int[] nums) {
        int a = nums[0];
        int b = nums[1];
        int c = nums[2];
        int count = 0;
        //判断是不是三角形
        if (a + b > c && a + c > b && b + c > a) {
            if (a == b) {
                count++;
            }
            if (b == c) {
                count++;
            }
            if (a == c) {
                count++;
            }
        } else {
            return "none";
        }
        if (count == 0) {
            return "scalene";
        }
        if (count == 1) {
            return "isosceles";
        }
        if (count == 3) {
            return "equilateral";
        }
        return "none";
    }



    //给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

    // 方法一 ，排序之后再返回，太慢了
    // Arrays.sort(nums);
    //        int res = nums.length;
    //        for (int i = 0; i < nums.length; i++) {
    //            if (nums[i] != i) {
    //                return i;
    //            }
    //        }
    //        return res;

    public int missingNumber(int[] nums) {
        // 方法二，使用位运算
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res ^= i;
            res ^= nums[i];
        }
        return res;
    }

    //    有效括号数量
    //    给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
    //
    //    有效字符串需满足：
    //
    //    左括号必须用相同类型的右括号闭合。
    //    左括号必须以正确的顺序闭合。
    //    每个右括号都有一个对应的相同类型的左括号。

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c: chars){
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else {
                if (stack.isEmpty() || c != stack.pop()) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    private int casePre(Character n) {
        switch (n) {
            case '(':

                return 0;
            case '{':

                return 1;
            case '[':

                return 2;
            case ')':

                return 3;
            case '}':

                return 4;
            case ']':

                return 5;
        }
        return 0;
    }


    //杨辉三角
    //方法一，就是，两边都是1 剩下的就是上一行的两两相加和
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> generate(int numRows) {
        if (numRows == 1) {
            res.add(Arrays.asList(1));
            return res;
        }
        //获取上一行
        generate(numRows - 1);
        ArrayList<Integer> l = new ArrayList<>(numRows);
        //把第一个和最后一个标记为1
        l.add(0,1);
        //添加中的的值
        for (int i = 1; i < numRows - 1; i++) {
            l.add(i,res.get(numRows-2).get(i - 1)+res.get(numRows-2).get(i));
        }
        l.add(numRows - 1,1);
        res.add(l);
        return res;
    }




    // 计算汉明重量
    //也就是计算一个数的 二进制之后有多少个1
    /*分治法思想
    代码的核心思想是分治：

    将32位数分成多个部分，分别计算每一部分的1的个数，然后逐步合并结果。
    通过位操作和加法，高效地累加1的个数。*/

    public int hammingWeight(int n) {
        // 计数
        n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
        n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
        n = (n * (0x01010101) >> 24);
        return n;

    }

    //计算汉明距离
    public int hammingDistance(int x, int y) {
        return hammingWeight(x ^ y);
    }

    //颠倒二进制
    //计算机里存贮的数值都是 补码
    //补码，求原码的操作其实就是对该补码再求补码

    // 0010 1001 0100 0001 1110 1001 110
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= (n &1);
            //一直向右移动一位，一位一位地把数字放到最前面
            n >>= 1;
        }
        return res;
    }
}
